{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Ways to Make Array With Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #combinatorics #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #组合数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToFillArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生成乘积数组的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>queries</code> ，其中 <code>queries[i] = [n<sub>i</sub>, k<sub>i</sub>]</code> 。第 <code>i</code> 个查询 <code>queries[i]</code> 要求构造长度为 <code>n<sub>i</sub></code> 、每个元素都是正整数的数组，且满足所有元素的乘积为 <code>k<sub>i</sub></code><sub> </sub>，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 。</p>\n",
    "\n",
    "<p>请你返回一个整数数组<em> </em><code>answer</code>，满足<em> </em><code>answer.length == queries.length</code> ，其中<em> </em><code>answer[i]</code>是第<em> </em><code>i</code> 个查询的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>queries = [[2,6],[5,1],[73,660]]\n",
    "<b>输出：</b>[4,1,50734910]\n",
    "<b>解释：</b>每个查询之间彼此独立。\n",
    "[2,6]：总共有 4 种方案得到长度为 2 且乘积为 6 的数组：[1,6]，[2,3]，[3,2]，[6,1]。\n",
    "[5,1]：总共有 1 种方案得到长度为 5 且乘积为 1 的数组：[1,1,1,1,1]。\n",
    "[73,660]：总共有 1050734917 种方案得到长度为 73 且乘积为 660 的数组。1050734917 对 10<sup>9</sup> + 7 取余得到 50734910 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]\n",
    "<b>输出：</b>[1,2,3,10,5]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= queries.length <= 10<sup>4</sup> </code></li>\n",
    "\t<li><code>1 <= n<sub>i</sub>, k<sub>i</sub> <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-ways-to-make-array-with-product](https://leetcode.cn/problems/count-ways-to-make-array-with-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-ways-to-make-array-with-product](https://leetcode.cn/problems/count-ways-to-make-array-with-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,6],[5,1],[73,660]]', '[[1,1],[2,2],[3,3],[4,4],[5,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# integer num = 2^a0 * 3^a1 * 5^a2 * ..\r\n",
    "# each prime factor pi of ai, can be distribute in to n slots in the array,\r\n",
    "# is a problem of distributing x balls in to n boxes, permit empty:\r\n",
    "# nCr(n + ai - 1, n - 1)\r\n",
    "# therefore answer to query of (num, n) is\r\n",
    "# sum(nCr(n + ai - 1, n - 1)), for all ai of num\r\n",
    "from math import comb\r\n",
    "from functools import cache, reduce\r\n",
    "primes: list[int] = list()\r\n",
    "\r\n",
    "def getPrimes() -> None:\r\n",
    "    vis = [False] * 10001\r\n",
    "    for i in range(2, 10001):\r\n",
    "        if vis[i]: continue\r\n",
    "        primes.append(i)\r\n",
    "        j = i\r\n",
    "        while j <= 10000:\r\n",
    "            vis[j] = True\r\n",
    "            j += i\r\n",
    "\r\n",
    "def getFactors(num: int):\r\n",
    "    for p in primes:\r\n",
    "        if p > num:\r\n",
    "            return\r\n",
    "        if num % p > 0: continue\r\n",
    "        cnt = 0\r\n",
    "        while num % p == 0:\r\n",
    "            cnt += 1\r\n",
    "            num //= p\r\n",
    "        yield cnt\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\r\n",
    "        if not primes: getPrimes()\r\n",
    "        return list(map(lambda q: reduce(lambda x, a: (x * cache(comb)(q[0] + a - 1, q[0] - 1)) % 1000000007, getFactors(q[1]), 1), queries))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def getPrimes(self, n):\n",
    "        primes = []\n",
    "        for i in range(2, n):\n",
    "            for j in range(2, i):\n",
    "                if(i % j == 0):\n",
    "                    break\n",
    "            primes.append(i)\n",
    "        return primes\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        primes = self.getPrimes(100)\n",
    "\n",
    "        for n, k in queries:\n",
    "            ways = 1\n",
    "            for prime in primes:\n",
    "                if prime > k:\n",
    "                    break\n",
    "                cnt = 0\n",
    "                while k % prime == 0:\n",
    "                    cnt += 1\n",
    "                    k /= prime\n",
    "                ways *= comb(n + cnt - 1, cnt)\n",
    "            if k > 1:\n",
    "                ways = ways * n\n",
    "            ans.append(ways % mod)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import math\n",
    "# get primes under 10**4 first \n",
    "dp = [0]*(100)\n",
    "i =2 \n",
    "primes = []\n",
    "while i<100:\n",
    "    if dp[i]==0:\n",
    "        primes.append(i)\n",
    "        dp[i] = 1 \n",
    "        k = 1\n",
    "        while i*k<100:\n",
    "            dp[i*k] = 1\n",
    "            k += 1\n",
    "    else:\n",
    "        i += 1\n",
    "        continue \n",
    "\n",
    "MODX = 10**9+7\n",
    "# comb_n = 10**4+5\n",
    "# comb = [[0]*comb_n for _ in range(comb_n)]\n",
    "# for i in range(comb_n):\n",
    "#     comb[i][0] = 1\n",
    "# for i in range(1,comb_n):\n",
    "#     for j in range(1,i+1):\n",
    "#         if i==j:\n",
    "#             comb[i][j] = 1\n",
    "#             continue \n",
    "#         comb[i][j] = comb[i-1][j-1]+comb[i-1][j]\n",
    "#         comb[i][j] %= MODX\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        MODX = 10**9+7\n",
    "        answers = []\n",
    "        for query in queries:\n",
    "            size, target = query\n",
    "            ways = 1\n",
    "            for x in primes:\n",
    "                if x>target:\n",
    "                    break \n",
    "                count = 0\n",
    "                while target>1 and target%x==0:\n",
    "                    count += 1\n",
    "                    target = target//x\n",
    "                ways *= math.comb(count+size-1,size-1)\n",
    "                ways  %= MODX\n",
    "            if target>1:\n",
    "                ways *= size \n",
    "            answers.append(ways%MODX)\n",
    "        return answers \n",
    "\n",
    "\n",
    "                    \n",
    "                \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        def repCombCount(n, goal):\n",
    "            factors = defaultdict(int)\n",
    "            i = 2\n",
    "            while i * i <= goal:\n",
    "                if goal % i == 0:\n",
    "                    factors[i] += 1\n",
    "                    goal //= i\n",
    "                else:\n",
    "                    i += 1\n",
    "            if goal > 1:\n",
    "                factors[goal] += 1\n",
    "\n",
    "            count = 1\n",
    "            for num in factors:\n",
    "                count *= comb(n + factors[num] - 1, factors[num])\n",
    "                count %= MOD\n",
    "            return count\n",
    "        return [repCombCount(q[0], q[1]) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "class Solution:\n",
    "    def buildPList(self):\n",
    "        m = int(1e4)\n",
    "        self.p_list = []\n",
    "        a = [1 for i in range(m+1)]\n",
    "        for i in range(2, m+1):\n",
    "            if a[i]:\n",
    "                self.p_list.append(i)\n",
    "                j = i<<1\n",
    "                while(j <=m):\n",
    "                    a[j] = 0\n",
    "                    j +=i\n",
    "        return\n",
    "\n",
    "    def FindFactors(self, k):\n",
    "        factors = dict()\n",
    "        res = k\n",
    "        i = 0\n",
    "        while(i<len(self.p_list) and res>1):\n",
    "            p = self.p_list[i]\n",
    "            while(res % p ==0):\n",
    "                if p not in factors:\n",
    "                    factors[p] =0\n",
    "                res /= p\n",
    "                factors[p]+=1\n",
    "            i +=1\n",
    "        return factors\n",
    "\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        dmod = int(1e9 + 7)\n",
    "        self.buildPList()\n",
    "        ans = []\n",
    "        getComb = lambda m,n: comb(m,n) % dmod\n",
    "\n",
    "        for q in queries:\n",
    "            n, k = q[0], q[1]\n",
    "            factors = self.FindFactors(k) # p:m pairs\n",
    "            cnt = 1\n",
    "            for m in factors.values(): # keys not important\n",
    "                cnt *= getComb(m-1+n, m) # Diaphragm method\n",
    "                cnt = cnt % dmod\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "\r\n",
    "\r\n",
    "MOD = 10 ** 9 + 7\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "    @staticmethod\r\n",
    "    def getPrimes(n):\r\n",
    "        primes = []\r\n",
    "        for i in range(2, n):\r\n",
    "            flag = 0\r\n",
    "            for j in range(2, int(i**0.5)+1):\r\n",
    "                if (i % j == 0):\r\n",
    "                    flag = 1\r\n",
    "                    break\r\n",
    "            if not flag: primes.append(i)\r\n",
    "        return primes\r\n",
    "   \r\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\r\n",
    "        result = []\r\n",
    "        \r\n",
    "        primes = self.getPrimes(100)\r\n",
    "\r\n",
    "        for query in queries:\r\n",
    "            n, k = query\r\n",
    "            ways = 1\r\n",
    "            for prime in primes:\r\n",
    "                if prime > k:\r\n",
    "                    break\r\n",
    "                cnt = 0\r\n",
    "                while k % prime == 0:\r\n",
    "                    # 尝试用 prime 分解 k\r\n",
    "                    cnt += 1\r\n",
    "                    k /= prime\r\n",
    "                ways *= math.comb(n + cnt - 1, cnt)\r\n",
    "\r\n",
    "            if k > 1:\r\n",
    "                # 如果最后 k > 1，那么说明 k 无法进一步被分解\r\n",
    "                # 此时 k 是一个比较大的质数，比如 2377\r\n",
    "                # 只要把 k 放在 n 个格子的任意一个位置，所以有 n 种放法\r\n",
    "                ways = ways * n\r\n",
    "            result.append(ways % MOD)\r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# get primes under 10**4 first \n",
    "dp = [0]*(10**4)\n",
    "i =2 \n",
    "primes = []\n",
    "while i<10**4:\n",
    "    if dp[i]==0:\n",
    "        primes.append(i)\n",
    "        dp[i] = 1 \n",
    "        k = 1\n",
    "        while i*k<10**4:\n",
    "            dp[i*k] = 1\n",
    "            k += 1\n",
    "    else:\n",
    "        i += 1\n",
    "        continue \n",
    "\n",
    "MODX = 10**9+7\n",
    "# comb_n = 10**4+5\n",
    "# comb = [[0]*comb_n for _ in range(comb_n)]\n",
    "# for i in range(comb_n):\n",
    "#     comb[i][0] = 1\n",
    "# for i in range(1,comb_n):\n",
    "#     for j in range(1,i+1):\n",
    "#         if i==j:\n",
    "#             comb[i][j] = 1\n",
    "#             continue \n",
    "#         comb[i][j] = comb[i-1][j-1]+comb[i-1][j]\n",
    "#         comb[i][j] %= MODX\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        MODX = 10**9+7\n",
    "        answers = []\n",
    "        for query in queries:\n",
    "            size, target = query\n",
    "            ways = 1\n",
    "            for x in primes:\n",
    "                if x>target:\n",
    "                    break \n",
    "                count = 0\n",
    "                while target>1 and target%x==0:\n",
    "                    count += 1\n",
    "                    target = target//x\n",
    "                ways *= math.comb(count+size-1,size-1)\n",
    "                ways  %= MODX\n",
    "            answers.append(ways)\n",
    "        return answers \n",
    "\n",
    "\n",
    "                    \n",
    "                \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import comb\n",
    "class Solution:\n",
    "    def buildPList(self):\n",
    "        m = int(1e4)\n",
    "        self.p_list = []\n",
    "        a = [1 for i in range(m+1)]\n",
    "        for i in range(2, m+1):\n",
    "            if a[i]:\n",
    "                self.p_list.append(i)\n",
    "                j = i<<1\n",
    "                while(j <=m):\n",
    "                    a[j] = 0\n",
    "                    j +=i\n",
    "        return\n",
    "\n",
    "    def FindFactors(self, k):\n",
    "        factors = dict()\n",
    "        res = k\n",
    "        i = 0\n",
    "        while(i<len(self.p_list) and res>1):\n",
    "            p = self.p_list[i]\n",
    "            while(res % p ==0):\n",
    "                if p not in factors:\n",
    "                    factors[p] =0\n",
    "                res /= p\n",
    "                factors[p]+=1\n",
    "            i +=1\n",
    "        return factors\n",
    "\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        dmod = int(1e9 + 7)\n",
    "        self.buildPList()\n",
    "        ans = []\n",
    "        getComb = lambda m,n: comb(m,n) % dmod\n",
    "\n",
    "        for q in queries:\n",
    "            n, k = q[0], q[1]\n",
    "            factors = self.FindFactors(k) # p:m pairs\n",
    "            cnt = 1\n",
    "            for m in factors.values(): # keys not important\n",
    "                cnt *= getComb(m-1+n, n-1) # Diaphragm method\n",
    "                cnt = cnt % dmod\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "def comb(n, r):\n",
    "    if r == 0:\n",
    "        return 1\n",
    "    if r > n:\n",
    "        return 0\n",
    "    res = 1\n",
    "    for i in range(1, r + 1):\n",
    "        res = res * (n - i + 1) // i\n",
    "    return res % MOD\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        def prime_factors(n):\n",
    "            i = 2\n",
    "            factors = {}\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors[i] = factors.get(i, 0) + 1\n",
    "            if n > 1:\n",
    "                factors[n] = factors.get(n, 0) + 1\n",
    "            return factors\n",
    "        \n",
    "        ans = []\n",
    "        for n, k in queries:\n",
    "            factors = prime_factors(k)\n",
    "            ways = 1\n",
    "            for e in factors.values():\n",
    "                ways = (ways * comb(n + e - 1, e)) % MOD\n",
    "            ans.append(ways)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "test = [i for i in range(10001)]\n",
    "for i in range(2, 10001):\n",
    "    if test[i] == i:\n",
    "        for j in range(i, 10001, i):\n",
    "            test[j] = min(test[j], i)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for n, k in queries:\n",
    "            c = Counter()\n",
    "            while test[k] > 1:\n",
    "                c[test[k]] += 1\n",
    "                k //= test[k]\n",
    "            res = 1\n",
    "            for i in c:\n",
    "                res *= comb(n + c[i] - 1, c[i])\n",
    "                res %= 1000000007\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 约数 预处理\n",
    "divisors = [[], []]\n",
    "for i in range(2, 10**4 + 1):\n",
    "    for j in range(2, int(i**0.5) + 1):\n",
    "        if i % j == 0:\n",
    "            divisors.append(divisors[i // j] + [j])\n",
    "            break\n",
    "    else:\n",
    "        divisors.append([i])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for i, j in queries:\n",
    "            c = Counter(divisors[j])\n",
    "            x = 1\n",
    "            for k in c.values():\n",
    "                x *= comb(i + k - 1, k)\n",
    "                x %= 10**9 + 7\n",
    "            res.append(x % (10**9 + 7))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxn = 10013\n",
    "MOD = 1000000007\n",
    "rs = [[] for _ in range(maxn)]\n",
    "for i in range(2, maxn):\n",
    "    if not rs[i]:\n",
    "        for j in range(i, maxn, i):\n",
    "            rs[j].append(0)\n",
    "            k = j\n",
    "            while k % i == 0:\n",
    "                rs[j][-1] += 1\n",
    "                k //= i\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for n, k in queries:\n",
    "            ans = 1\n",
    "            for r in rs[k]:\n",
    "                ans = ans * comb(n + r - 1, r) % MOD\n",
    "            res.append(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "MX = 10 ** 4 + 1\n",
    "ks = [[] for _ in range(MX)]\n",
    "for i in range(2, MX):\n",
    "    p, x = 2, i\n",
    "    while p ** 2 <= x:\n",
    "        if x % p == 0:\n",
    "            k = 1\n",
    "            x //= p\n",
    "            while x % p == 0:\n",
    "                x //= p\n",
    "                k += 1\n",
    "            ks[i].append(k)\n",
    "        p += 1\n",
    "    if x > 1: ks[i].append(1)\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        def process(n, val):\n",
    "            ans = 1\n",
    "            for k in ks[val]:\n",
    "                ans *= comb(n + k - 1, k)\n",
    "                ans %= MOD\n",
    "            return ans\n",
    "        res = []\n",
    "        for n, val in queries:\n",
    "            res.append(process(n, val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 2023-09-22 16:19:12\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        res = [0] * n\n",
    "\n",
    "        @cache\n",
    "        def f(n, k):\n",
    "            if k == 1:\n",
    "                return 1\n",
    "            res = 1\n",
    "            i = 2\n",
    "            while i * i <= k:\n",
    "                if k % i == 0:\n",
    "                    y = 0\n",
    "                    while k % i == 0:\n",
    "                        y += 1\n",
    "                        k //= i\n",
    "                    res = res * comb(n + y - 1, y) % mod\n",
    "                i += 1\n",
    "            if k > 1:\n",
    "                res = res * n % mod\n",
    "            return res % mod\n",
    "\n",
    "        for i, (x, k) in sorted(enumerate(queries), key=lambda e: e[1][1]):\n",
    "            res[i] = f(x, k)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Ball:\n",
    "    \"\"\"https://qiita.com/drken/items/f2ea4b58b0d21621bd51\"\"\"\n",
    "\n",
    "    __slots__ = (\"_fac\", \"_ifac\", \"_inv\", \"_mod\")\n",
    "\n",
    "    def __init__(self, size: int, mod: int) -> None:\n",
    "        self._mod = mod\n",
    "        self._fac = [1]\n",
    "        self._ifac = [1]\n",
    "        self._inv = [1]\n",
    "        self._expand(size)\n",
    "\n",
    "    def query(\n",
    "        self,\n",
    "        n: int,\n",
    "        k: int,\n",
    "        *,\n",
    "        isBallSame: bool,\n",
    "        isBoxSame: bool,\n",
    "        atMostOneBallPerBox=False,\n",
    "        noLimitWithBox=False,\n",
    "        atLeastOneBallPerBox=False,\n",
    "    ) -> int:\n",
    "        \"\"\"n个球放入k个盒子的方案数.\n",
    "\n",
    "        Args:\n",
    "            isBallSame (bool): 球是否有区别.\n",
    "            isBoxSame (bool): 盒子是否有区别.\n",
    "            atMostOneBalPerBox (bool, optional): 每个盒子最多放一个球.\n",
    "            noLimitWithBox (bool, optional): 每个盒子可以放任意个球.\n",
    "            atLeastOneBallPerBox (bool, optional): 每个盒子至少放一个球.\n",
    "        \"\"\"\n",
    "        limits = (atMostOneBallPerBox, noLimitWithBox, atLeastOneBallPerBox)\n",
    "        assert limits.count(True) == 1, \"Must have one limit and only one limit with box.\"\n",
    "        if isBallSame and isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve1(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve2(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve3(n, k)\n",
    "        if not isBallSame and isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve4(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve5(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve6(n, k)\n",
    "        if isBallSame and not isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve7(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve8(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve9(n, k)\n",
    "        if not isBallSame and not isBoxSame:\n",
    "            if atMostOneBallPerBox:\n",
    "                return self._solve10(n, k)\n",
    "            if noLimitWithBox:\n",
    "                return self._solve11(n, k)\n",
    "            if atLeastOneBallPerBox:\n",
    "                return self._solve12(n, k)\n",
    "\n",
    "        raise Exception(\"Unreachable code.\")\n",
    "\n",
    "    def _solve1(self, n: int, k: int) -> int:\n",
    "        \"\"\"有区别的球放入有区别的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return self.P(n, k)\n",
    "\n",
    "    def _solve2(self, n: int, k: int) -> int:\n",
    "        \"\"\"有区别的球放入有区别的盒子(每个盒子可以放任意个球).\"\"\"\n",
    "        return pow(k, n, self._mod)\n",
    "\n",
    "    def _solve3(self, n: int, k: int) -> int:\n",
    "        \"\"\"有区别的球放入有区别的盒子(每个盒子至少放一个球).\n",
    "        容斥原理:用总方案数减去不合法的方案数.\n",
    "        O(k*logn)\n",
    "        \"\"\"\n",
    "        mod = self._mod\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            if (k - i) & 1:\n",
    "                res -= self.C(k, i) * pow(i, n, mod)\n",
    "            else:\n",
    "                res += self.C(k, i) * pow(i, n, mod)\n",
    "            res %= mod\n",
    "        return res\n",
    "\n",
    "    def _solve4(self, n: int, k: int) -> int:\n",
    "        \"\"\"无区别的球放入有区别的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return self.C(n, k)\n",
    "\n",
    "    def _solve5(self, n: int, k: int) -> int:\n",
    "        \"\"\"无区别的球放入有区别的盒子(每个盒子可以放任意个球).\"\"\"\n",
    "        return self.C(n + k - 1, n)\n",
    "\n",
    "    def _solve6(self, n: int, k: int) -> int:\n",
    "        \"\"\"无区别的球放入有区别的盒子(每个盒子至少放一个球).\"\"\"\n",
    "        return self.C(n - 1, k - 1)\n",
    "\n",
    "    def _solve7(self, n: int, k: int) -> int:\n",
    "        \"\"\"有区别的球放入无区别的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return 0 if n > k else 1\n",
    "\n",
    "    def _solve8(self, n: int, k: int) -> int:\n",
    "        \"\"\"有区别的球放入无区别的盒子(每个盒子可以放任意个球).\n",
    "        贝尔数B(n,k).\n",
    "        O(min(n,k)*logn).\n",
    "        \"\"\"\n",
    "        return self.bell(n, k)\n",
    "\n",
    "    def _solve9(self, n: int, k: int) -> int:\n",
    "        \"\"\"有区别的球放入无区别的盒子(每个盒子至少放一个球).\n",
    "        第二类斯特林数S(n,k).\n",
    "        O(k*logn).\n",
    "        \"\"\"\n",
    "        return self.stirling2(n, k)\n",
    "\n",
    "    def _solve10(self, n: int, k: int) -> int:\n",
    "        \"\"\"无区别的球放入无区别的盒子(每个盒子最多放一个球).\"\"\"\n",
    "        return 0 if n > k else 1\n",
    "\n",
    "    def _solve11(self, n: int, k: int) -> int:\n",
    "        \"\"\"无区别的球放入无区别的盒子(每个盒子可以放任意个球).\n",
    "        分割数P(n,k).\n",
    "        \"\"\"\n",
    "        return self.partition(n, k)\n",
    "\n",
    "    def _solve12(self, n: int, k: int) -> int:\n",
    "        \"\"\"无区别的球放入无区别的盒子(每个盒子至少放一个球).\n",
    "        分割数P(n-k,k).\n",
    "        \"\"\"\n",
    "        if n < k:\n",
    "            return 0\n",
    "        return self.partition(n - k, k)\n",
    "\n",
    "    def fac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._fac[k]\n",
    "\n",
    "    def ifac(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._ifac[k]\n",
    "\n",
    "    def inv(self, k: int) -> int:\n",
    "        self._expand(k)\n",
    "        return self._inv[k]\n",
    "\n",
    "    def C(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(k) % mod * self.ifac(n - k) % mod\n",
    "\n",
    "    def P(self, n: int, k: int) -> int:\n",
    "        if n < 0 or k < 0 or n < k:\n",
    "            return 0\n",
    "        mod = self._mod\n",
    "        return self.fac(n) * self.ifac(n - k) % mod\n",
    "\n",
    "    def H(self, n: int, k: int) -> int:\n",
    "        \"\"\"可重复选取元素的组合数\"\"\"\n",
    "        if n == 0:\n",
    "            return 1 if k == 0 else 0\n",
    "        return self.C(n + k - 1, k)\n",
    "\n",
    "    def put(self, n: int, k: int) -> int:\n",
    "        \"\"\"n个相同的球放入k个不同的盒子(盒子可放任意个球)的方案数.\"\"\"\n",
    "        return self.C(n + k - 1, n)\n",
    "\n",
    "    def partition(self, n: int, k: int) -> int:\n",
    "        \"\"\"O(n*k)\"\"\"\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                if i >= j:\n",
    "                    dp[i][j] = dp[i][j - 1] + dp[i - j][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return dp[n][k]\n",
    "\n",
    "    def bell(self, n: int, k: int) -> int:\n",
    "        \"\"\"O(min(n,k)*logn)\"\"\"\n",
    "        if k > n:\n",
    "            k = n\n",
    "        mod = self._mod\n",
    "        jsum = [0] * (k + 2)\n",
    "        for j in range(k + 1):\n",
    "            add = self.ifac(j)\n",
    "            if j & 1:\n",
    "                jsum[j + 1] = (jsum[j] - add) % mod\n",
    "            else:\n",
    "                jsum[j + 1] = (jsum[j] + add) % mod\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            res += pow(i, n, mod) * self.ifac(i) % MOD * jsum[k - i + 1]\n",
    "            res %= mod\n",
    "        return res\n",
    "\n",
    "    def stirling2(self, n: int, k: int) -> int:\n",
    "        \"\"\"O(k*logn)\"\"\"\n",
    "        mod = self._mod\n",
    "        res = 0\n",
    "        for i in range(k + 1):\n",
    "            if (k - i) & 1:\n",
    "                res -= self.C(k, i) * pow(i, n, mod)\n",
    "            else:\n",
    "                res += self.C(k, i) * pow(i, n, mod)\n",
    "            res %= mod\n",
    "        return res * self.ifac(k) % mod\n",
    "\n",
    "    def _expand(self, size: int) -> None:\n",
    "        if len(self._fac) < size + 1:\n",
    "            mod = self._mod\n",
    "            preSize = len(self._fac)\n",
    "            diff = size + 1 - preSize\n",
    "            self._fac += [1] * diff\n",
    "            self._ifac += [1] * diff\n",
    "            self._inv += [1] * diff\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._fac[i] = self._fac[i - 1] * i % mod\n",
    "            self._ifac[size] = pow(self._fac[size], mod - 2, mod)  # !modInv\n",
    "            for i in range(size - 1, preSize - 1, -1):\n",
    "                self._ifac[i] = self._ifac[i + 1] * (i + 1) % mod\n",
    "            for i in range(preSize, size + 1):\n",
    "                self._inv[i] = self._ifac[i] * self._fac[i - 1] % mod\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "\n",
    "\n",
    "ball=Ball(10**4,10**9+7)\n",
    "\n",
    "pt=PrimeTable(10**4+5)\n",
    "\n",
    "mod=10**9+7\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        res=[]\n",
    "        for L,T in queries:\n",
    "            ans=1\n",
    "            for p,c in pt.prime_factorization(T): \n",
    "                #c个相同的球，放入L个不同的盒子，可空的方案数\n",
    "                ans*=ball._solve5(c,L)\n",
    "                ans%=mod\n",
    "            res.append(ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        def getprimes(x):\n",
    "            i=2\n",
    "            res=[]\n",
    "            while x!=1:\n",
    "                while x%i==0:\n",
    "                    res.append(i)\n",
    "                    x=x//i\n",
    "                i+=1\n",
    "                if i>isqrt(x):\n",
    "                    i=x\n",
    "            return list(Counter(res).values())\n",
    "        n0=max(q[0] for q in queries)+1\n",
    "        dp=[[0]*15 for _ in range(n0)]\n",
    "        M=10**9+7\n",
    "        for i in range(15):\n",
    "            dp[1][i]=1\n",
    "        for i in range(2,n0):\n",
    "            dp[i][0]=dp[i-1][0]\n",
    "            for j in range(1,15):\n",
    "                #dp[n][m]=sum(dp[n-1][i]for i in range(m+1))\n",
    "                dp[i][j]=dp[i][j-1]+dp[i-1][j]\n",
    "                dp[i][j]%=M\n",
    "        wtfa=[]\n",
    "        for n,k in queries:\n",
    "            cntlist=getprimes(k)\n",
    "            #print(cntlist)\n",
    "            tmp=1\n",
    "            for i in cntlist:\n",
    "                tmp*=dp[n][i]\n",
    "                tmp%=M\n",
    "            wtfa.append(tmp)\n",
    "        return wtfa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxNum = 10 ** 4 \n",
    "maxLog = 13\n",
    "mod = 10 ** 9 + 7\n",
    "C = [[0 for _ in range(maxLog + 1)] for _ in range(maxNum + maxLog)]\n",
    "C[0][0] = 1 \n",
    "for i in range(1, maxNum + maxLog):\n",
    "    C[i][0] = 1 \n",
    "    for j in range(1, maxLog + 1):\n",
    "        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]\n",
    "        C[i][j] %= mod \n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for n, k in queries:\n",
    "            ans = 1 \n",
    "            p = 2 \n",
    "            while p * p <= k:\n",
    "                if k % p == 0:\n",
    "                    cnt = 0\n",
    "                    while k % p == 0:\n",
    "                        cnt += 1 \n",
    "                        k //= p\n",
    "                    ans = ans * C[n + cnt - 1][cnt] % (10 ** 9 + 7)\n",
    "                p += 1 \n",
    "            if k > 1:\n",
    "                ans = ans * C[n + 1 - 1][1] % (10 ** 9 + 7)\n",
    "            res.append(ans)\n",
    "        return res \n",
    "\n",
    "\n",
    "        res = []\n",
    "        mod = 10 ** 9 + 7 \n",
    "        for n, k in queries:\n",
    "            p = 2 \n",
    "            ans = 1 \n",
    "            while p * p <= k:\n",
    "                if k % p == 0:\n",
    "                    cnt = 0\n",
    "                    while k % p == 0:\n",
    "                        k //= p \n",
    "                        cnt += 1 \n",
    "                    ans = ans * C[n + cnt - 1][cnt] % mod \n",
    "                p += 1 \n",
    "            if k > 1:\n",
    "                ans = ans * C[n + 1 - 1][1] % mod\n",
    "            res.append(ans)\n",
    "        return res  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        def getprimes(x):\n",
    "            i=2\n",
    "            res=[]\n",
    "            while x!=1:\n",
    "                while x%i==0:\n",
    "                    res.append(i)\n",
    "                    x=x//i\n",
    "                i+=1\n",
    "            return list(Counter(res).values())\n",
    "        n0=max(q[0] for q in queries)+1\n",
    "        dp=[[0]*15 for _ in range(n0)]\n",
    "        M=10**9+7\n",
    "        for i in range(15):\n",
    "            dp[1][i]=1\n",
    "        for i in range(2,n0):\n",
    "            dp[i][0]=dp[i-1][0]\n",
    "            for j in range(1,15):\n",
    "                #dp[n][m]=sum(dp[n-1][i]for i in range(m+1))\n",
    "                dp[i][j]=dp[i][j-1]+dp[i-1][j]\n",
    "        wtfa=[]\n",
    "        for n,k in queries:\n",
    "            cntlist=getprimes(k)\n",
    "            #print(cntlist)\n",
    "            tmp=1\n",
    "            for i in cntlist:\n",
    "                tmp*=dp[n][i]\n",
    "                tmp%=M\n",
    "            wtfa.append(tmp)\n",
    "        return wtfa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:\n",
    "        def getprimes(x):\n",
    "            i=2\n",
    "            res=[]\n",
    "            while x!=1:\n",
    "                while x%i==0:\n",
    "                    res.append(i)\n",
    "                    x=x//i\n",
    "                i+=1\n",
    "            return list(Counter(res).values())\n",
    "        n0=max(q[0] for q in queries)+1\n",
    "        dp=[[0]*16 for _ in range(n0)]\n",
    "        M=10**9+7\n",
    "        for i in range(16):\n",
    "            dp[1][i]=1\n",
    "        for i in range(2,n0):\n",
    "            dp[i][0]=dp[i-1][0]\n",
    "            for j in range(1,16):\n",
    "                #dp[n][m]=sum(dp[n-1][i]for i in range(m+1))\n",
    "                dp[i][j]=dp[i][j-1]+dp[i-1][j]\n",
    "        wtfa=[]\n",
    "        for n,k in queries:\n",
    "            cntlist=getprimes(k)\n",
    "            #print(cntlist)\n",
    "            tmp=1\n",
    "            for i in cntlist:\n",
    "                tmp*=dp[n][i]\n",
    "                tmp%=M\n",
    "            wtfa.append(tmp)\n",
    "        return wtfa"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
